/*
 * @Author: liusheng
 * @Date: 2022-03-28 11:49:02
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 19:53:27
 * @Description: 剑指 Offer II 002. 二进制加法
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 剑指 Offer II 002. 二进制加法
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

 

示例 1:

输入: a = "11", b = "10"
输出: "101"
示例 2:

输入: a = "1010", b = "1011"
输出: "10101"
 

提示：

每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。
 

注意：本题与主站 67 题相同：https://leetcode-cn.com/problems/add-binary/

通过次数34,796  提交次数63,325
 */

#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.size() - 1;
        int j = b.size() - 1;
        string result;
        int carry = 0;
        while( i >= 0 && j >=0 )
        {
            int r = a[i--] + b[j--] + carry -96;

            if( r == 2 )
            {
                result.push_back('0');
                carry = 1;
            }
            else if(r == 3)
            {
                result.push_back('1');
                carry = 1;
            }
            else if(r == 1)
            {
                result.push_back('1');
                carry = 0;
            }
            else
            {
                result.push_back('0');
                carry = 0;
            }
        }

        if(carry && i == -1 && j == -1)
        {
            result.push_back('1');
            carry = 0;
        }

        while(i >= 0)
        {
            char r = a[i--] + carry - 48;

            if( r == 2 )
            {
                result.push_back('0');
                carry = 1;
            }
            else if(r == 1)
            {
                result.push_back('1');
                carry = 0;
            }
            else
            {
                result.push_back('0');
                carry = 0;
            }
        }

        while( j >= 0)
        {
            char r = b[j--] + carry - 48;
            if( r == 2 )
            {
                result.push_back('0');
                carry = 1;
            }
            else if(r == 1)
            {
                result.push_back('1');
                carry = 0;
            }
            else
            {
                result.push_back('0');
                carry = 0;
            }
        }


        if(carry)
        {
            result.push_back('1');
        }
        std::reverse(result.begin(),result.end());
        return result;
    }

    string addBinary2(string a, string b) {
        int aLength = a.size();
        int bLength = b.size();
        int maxLength = aLength > bLength ? aLength : bLength;
        string result;
        int carry = 0;
        for (int i = 0; i < maxLength; ++i)
        {
            if(i < aLength)
            {
                carry += a[aLength - 1 - i] - '0';
            }
            if(i < bLength)
            {
                carry += b[bLength - 1 -i] - '0';
            }
            result.push_back(carry%2 + '0');
            carry /= 2;
        }

        if(carry)
        {
            result.push_back('1');
        }

        std::reverse(result.begin(),result.end());
        return result;
    }
};